Slovarji III

Kraji in reči

V nalogi se bomo igrali s slovarji, ki opisujejo, kje se nahaja kakšen kraj. Slovar je lahko recimo, tak

svet = {
    "Evropa": {
        "Slovenija": {
            "Gorenjska": {
                "Kranj": {},
                "Radovljica": {},
                "Zali log": {},
            },
            "Štajerska": {
                "Maribor": {},
                "Celje": {}
            },
            "Osrednja": {
                "Ljubljana": {
                    "Vič": {
                        "FMF": {
                            "2.02": {
                                "tretja vrsta desno": {
                                    "peti stol z desne": {
                                        "Benjamin": {}
                                    }
                                }
                            }
                        }
                    },
                    "Šiška": {}
                }
            }
        },
        "Nemčija": {
            "Bavarska": {
                "Munchen": {}
            },
            "Berlin": {}
        },
    },
    "Amerika": {
        "ZDA": {
            "Teksas": {
                "Houston": {},
                "Austin": {}
            },
            "Kalifornija": {
                "San Francisco": {}
            },
            "Anchorage": {}
        },
        "Kanada": {}
    },
    "Azija": {
        "Osaka": {}
    }
   }

Ključi slovarja so torej nizi, vsebine pa so slovarji, ki so lahko tudi prazni. Namig: Oglejte si kako preveriti, ali je neka stuktura prazna,

1. podnaloga

Napiši funkcijo vrniVse(kraji), ki kot argument dobi slovar, kakršen je gornji, in vrne po abecedi urejen seznam vseh krajev in reči v njem.

Uradna rešitev

def vrniVse(kraji):
    '''po abesedi urejen seznam vseh krajev in reči v slovarju '''
    if not kraji : # če je slovar prazen
        return []
    seznamVseh = []
    for el in kraji:
        # dodamo ključ
        seznamVseh.append(el)
        # in vse elemente slovarja, ki je vrednost
        seznamVseh += vrniVse(kraji[el])
    return sorted(seznamVseh)

2. podnaloga

Napiši funkcijo prestej(kraji), ki vrne število vseh krajev in reči, ki se pojavijo v podanem slovarju.

Uradna rešitev

def prestej(kraji):
    '''koliko je stvari v slovarju kraji'''
    # v praznem slovarju ni stvari
    if len(kraji) == 0:
        return 0
    # pregledamo vse elemente slovarja in prištejemo 1 za ključ
    # in ustrezno število stvari v pripdajočem podslovarju
    koliko = 0
    for slovar in kraji.values():
        koliko += 1 # za ključ!
        kolikoVPodsl = prestej(slovar)
        koliko += kolikoVPodsl
    return koliko

# načeloma je prvi stavek if odveč, zato lahko napišemo
def prestejV2(kraji):
    '''koliko je stvari v slovarju kraji'''
    # pregledamo vse elemente slovarja in prištejemo 1 za ključ
    # in ustrezno število stvari v pripdajočem podslovarju
    koliko = 0
    for slovar in kraji.values():
        koliko += 1 # za ključ!
        kolikoVPodsl = prestejV2(slovar)
        koliko += kolikoVPodsl
    return koliko

3. podnaloga

Denimo, da imamo slovar (kot sta kraji in svet), ki kot vrednosti spet vsebuje slovarje. Sestavi funkcijo najSlovar(slovar), ki vrne tisti slovar, ki vsebuje največ ključev.

Uradna rešitev

def najSlovar(slovar) :
    ''' V slovarju slovarjev vrnemo slovar, ki vsebuje največ ključev '''
    if not slovar : # če je slovar prazen
        return slovar
    #kandidat za največjega je kar ta slovar
    kanNajSlovar = slovar
    # morda se v kakšni vrednosti skriva večji slovar
    for kljuc in slovar:
        # pogledamo najSlovar v ustrezni vrednosti
        vrednost = slovar[kljuc]
        kandidat = najSlovar(vrednost)
        if len(kandidat) > len(kanNajSlovar) : # našli smo boljšega
            kanNajSlovar = kandidat
    return kanNajSlovar

4. podnaloga

Sestavi funkcijo jeVSlovarju(slovar, nekaj), ki ugotovi, ali je v slovarju slovar tudi niz nekaj (bodisi kot ključ, bodisi kot vrednost)

Uradna rešitev

def jeVSlovarju(slovar, nekaj) :
    ''' Ali je v slovarju slovar tudi niz nekaj (bodisi kot ključ, bodis kot vrednost)'''
    if not slovar : # če je slovar prazen
        return False
    # pregledamo vse ključe
    for kljuc in slovar:
        # pogledamo če je morda to ta ključ
        if kljuc == nekaj:
            return True
        # je morda v vrednosti, ki je slovar
        if jeVSlovarju(slovar[kljuc], nekaj):
            return True
    # nekaj ni bil ne ključ, en v kateri od vrenosti, torej je ni!
    return False

5. podnaloga

Sestavi funkcijo vrniVrednost(slovar, nekaj), ki vrne tisto vrednost iz slovarja slovarjev slovar, ki pripada ključu nekaj Če pa v slovarju slovarjev nekaj ni ključ, naj vrne None

Uradna rešitev

def vrniVrednost(slovar, nekaj) :
    ''' Ali je v slovarju slovar tudi niz nekaj (bodisi kot ključ, bodis kot vrednost)'''
    if not slovar : # če je slovar prazen
        return None
    # pregledamo vse ključe
    for kljuc in slovar:
        # pogledamo če je morda to ta ključ
        if kljuc == nekaj:
            return slovar[kljuc]
        # je morda v vrednosti, ki je slovar
        kaj = vrniVrednost(slovar[kljuc], nekaj)
        if kaj != None : # torej je bilo
           return kaj
    # nekaj nismo našli v nobenem slovarju, torej je ni!
    return None

Veliki šef in njegovi podrejeni

V nekem uspešnem podjetju ima skoraj vsak zaposleni svojega šefa. Seveda imajo tudi šefi svoje šefe in ti spet svoje šefe itn. Dobili smo podatke o hierarhiji v podjetju in ugotovili, da velja naslednje:

Napisali bomo nekaj funkcij, s katerimi bomo preučili razmere v podjetju.

1. podnaloga

Podatke smo dobili v obliki seznama parov oblike (uslužbenec, šef). Vsi uslužbenci so predstavljeni z nizi (ki so običajno njihova imena oz. priimki). Zgled:

[('Mojca', 'Tilen'), ('Andrej', 'Tilen'), ('Tilen', 'Zoran')]

Komentar: Tilen ima pod seboj dva podrejena (Andreja in Mojco), njegovi šef pa je Zoran. Zoran nima šefa, vsi ostali pa so njegovi podrejeni.

Napišite funkcijo slovarSefov(seznam), ki bo iz zgoraj opisanega seznama zgradila slovar šefov. Ključi v seznamu naj bodo uslužbenci, vrednosti pa njihovi šefi. Zgled:

>>> slovarSefov([('Mojca', 'Tilen'), ('Andrej', 'Tilen'), ('Tilen', 'Zoran')])
{'Andrej': 'Tilen', 'Mojca': 'Tilen', 'Tilen': 'Zoran'}

Uradna rešitev

def slovarSefov(seznam):
    '''Glede na zgornji opis vrne slovar šefov'''
    slovar = {}
    for usluzbenec, sef in seznam:
        slovar[usluzbenec] = sef
    return slovar

2. podnaloga

Napišite funkcijo neposrednoPodrejeni(seznam), ki bo iz zgoraj opisanega seznama sestavila slovar neposredno podrejenih. Vrednost pri vsakem ključu naj bo množica tistih uslužbencev, ki imajo le-ta ključ za svojega šefa. Zgled:

>>> neposrednoPodrejeni([('Mojca', 'Tilen'), ('Andrej', 'Tilen'), ('Tilen', 'Zoran')])
{'Zoran': {'Tilen'}, 'Tilen': {'Andrej', 'Mojca'}}

Zoranu je torej neposredno podrejen le Tilen, Tilnu pa sta podrejena tako Andrej kot Mojca.

Uradna rešitev

def neposrednoPodrejeni(seznam):
    '''Glede na zgornji opis vrne slovar šef : množica neposredno podrejenih'''
    podrejeni = {}
    for usluzbenec, sef in seznam: # sprehodimo se po parih iz seznama
        if sef not in podrejeni: # če smo našli novega šefa
            podrejeni[sef] = set() # je potrebno narediti nov vnos v slovar
        podrejeni[sef].add(usluzbenec)
    return podrejeni

3. podnaloga

Sestavite funkcijo verigaNadrejenih(usluzbenec, slovar), ki kot prvi argument dobi niz, ki predstavlja nekega uslužbenca, kot drugi argument pa dobi slovar šefov (v obliki kot ga vrne funkcija slovarSefov). Funkcija naj sestavi seznam, ki po vrsti vsebuje: šefa osebe usluzbenec, šefa od njegovega šefa itn. (dokler končno ne pridemo do osebe, ki nima šefa). Zgled:

>>> verigaNadrejenih('Mojca', {'Andrej': 'Tilen', 'Mojca': 'Tilen', 'Tilen': 'Zoran'})
['Tilen', 'Zoran']

Mojci je nadrejen Tilen, kateremu je nadrejen Zoran, torej sta Mojčina šefa Tilen in Zoran.

Uradna rešitev

def verigaNadrejenih(usluzbenec, slovar):
    '''sestavi seznam, ki predstavlja verigo nadreejenih'''
    # če oseba nima šefa, je njegova veriga prazna
    # oseba nima šefa, če se ne pojavi kot ključ
    if usluzbenec not in slovar.keys():
        return []
    # uslužbenec ima šefa!
    sef = slovar[usluzbenec]
    seznamNadrejenih = [sef]
    # določimo verigo nadrejenih od šefa
    verNadrSef = verigaNadrejenih(sef, slovar)
    # združimo seznama
    seznamNadrejenih = seznamNadrejenih + verNadrSef
    return seznamNadrejenih

def verigaNadrejenihV2(usluzbenec, slovar):
    '''Glede na zgornji opis vrne zaporedni seznam oseb, ki so uslužbencu nadrejeni'''
    '''brez rekurzije'''
    veriga = []
    while usluzbenec in slovar: # če uslužbenec ima šefa (ko ga ne bo imel, smo na koncu verige!)
        usluzbenec = slovar[usluzbenec] # vzamemo njegovega šefa - v naslednjem koraku bomo vzeli njegovega šefa ...
        veriga.append(usluzbenec) # in ga dodamo
    return veriga

4. podnaloga

Sestavite funkcijo mnozicaPodrejenih(usluzbenec, slovar), ki kot prvi argument dobi ime uslužbenca, kot drugi argument pa slovar neposredno podrejenih (v obliki kot ga vrne funkcija neposrednoPodrejeni). Funkcija naj sestavi in vrne množico vseh tistih oseb, ki so (posredno ali neposredno) podrejeni osebi usluzbenec. Zgled:

>>> mnozicaPodrejenih('Zoran', {'Zoran': {'Tilen'}, 'Tilen': {'Andrej', 'Mojca'}, 'Mojca' : {'Urša'}})
{'Andrej', 'Mojca', 'Tilen', 'Urša'}

Zoranju je neposredno podrejen Tilen, torej sta mu podrejena tudi Tilnova podrejena Andrej in Mojca, ter Urša, ker je ta podrejena Mojci.

Uradna rešitev

def mnozicaPodrejenih(usluzbenec, slovar):
    '''vrne  _množico_ vseh tistih oseb, ki so (posredno ali
       neposredno) podrejeni osebi `usluzbenec`.'''
    # komentarjev NAMENOMA ni !
    dodaj = [usluzbenec]
    podrejeni = set()
    while len(dodaj) > 0:
        u = dodaj[-1]
        del dodaj[-1]
        if u not in slovar:
            continue
        for v in slovar[u]:
            if v not in podrejeni:
                dodaj.append(v)
            podrejeni.add(v)
    return podrejeni

5. podnaloga

Tistemu uslužbencu, za katerega velja:

pravimo big boss. Sestavite funkcijo bigBoss(slovar), ki kot argument dobi slovar nadrejenih in vrne ime osebe, ki je big boss v podjetju oz. vrednost None, če to podjetje nima big boss-a. Zgled:

>>> bigBoss({'Andrej': 'Tilen', 'Mojca': 'Tilen', 'Tilen': 'Zoran'})
'Zoran'

Uradna rešitev

def bigBoss(slovar):
    '''nekdo, ki nima šefa in je šef vsem ostalim'''
    if len(slovar) == 0:
        return None # tak slovar ga nima!
    bigBoss = list(slovar.keys())[0] # kandidat za velikega šefa (če ne bo imel nadrejenih!)
    nadrejeni = verigaNadrejenih(bigBoss, slovar) # kdo so kandidatu nadrejeni?
    if len(nadrejeni) > 0: # če je prejšnji kandidat imel nadrejene
        bigBoss = nadrejeni[-1] # je samo zadnji kandidat za velikega šefa
    # dobili smo kandidata za big boss-a
    for uslužbenec in slovar: # pregledamo vse uslužbence
        if uslužbenec == bigBoss: # kandidata spustimo
            continue
        nadrejeni = verigaNadrejenih(uslužbenec, slovar) # pogledamo vse uslužbencu nadrejene
        if (len(nadrejeni) == 0) or (nadrejeni[-1] != bigBoss): # če jih ni, potem bigBNoss ni nadrejeni temu, torej ni veliki šef!
            return None                                         # ali pa najvišji nadrejeni temu uslužbencu ni bil naš veliki šef - v firmi velikega šefa ni
    return bigBoss

Permutacije se vračajo

Ker ste v komentarjih napisali, da je ukvarjanje s permutacijami vaša najbolj priljubbljena tema, se permutacije vračajo v vsem svojem sijaju!

V slovarju imamo shranjeno permutacijo naravnih števil od $1$ do $n$. Na primer permutacijo, ki slika $1$ v $3$, $3$ v $1$, število $2$ pa pusti pri miru, zapišemo s slovarjem {1: 3, 2: 2, 3: 1}.

Pri vseh nalogah predpostavite, da je število x zagotovo element permutacije. Prav tako tudi to, da je permutacija pravilna.

1. podnaloga

Le za ogrevanje (naloga "ne šteje") rešite naslednjo nalogo:

Sestavite funkcijo slika(permutacija, x), vrne pa sliko števila x s podano permutacijo.

Uradna rešitev

def slika(permutacija, x):
    return permutacija[x]

2. podnaloga

Sestavite funkcijo jePermutacija(slovar), ki vrne True, če dan slovar predstavlja permutacijo, in False sicer.

Npr. slovar {1: 3, 3: 1} ni permutacija, saj ne vemo, kam se slika 2. Tudi {1: 3, 2: 2, 3: 2, 4: 1} ni slovar, saj 4 ni slika nobenega števila!

Uradna rešitev

def jePermutacija(slovar):
    # Za vsa števila od 1 do n bomo pogledali, če nastopajo tako v domeni
    # kot v sliki permutacije. Imeli bomo seznam je_v_domeni, ki ima na
    # mestu i - 1 zapisano, če smo ugotovili, da i je v domeni permutacije.
    # Podobno storimo za sliko.
    n = len(slovar)
    je_v_domeni = [False for i in range(n)]
    je_v_sliki = [False for i in range(n)]

    # Nato gremo čez vse ključe k in pripadajoče vrednosti v v slovarju.
    # Če sta tako k kot v med 1 in n, označimo, da sta v domeni in sliki,
    # sicer pa vemo, da slovar ne predstavlja permutacije.
    for k, v in slovar.items():
        if 1 <= k <= n and 1 <= v <= n:
            je_v_domeni[k - 1] = True
            je_v_sliki[v - 1] = True
        else:
            return False

    # Na koncu pogledamo, ali so v domeni in sliki nastopala vsa števila.
    # Funkcija all vrne True natanko takrat, ko so vsi elementi v seznamu
    # enaki True.
    return all(je_v_domeni) and all(je_v_sliki)

3. podnaloga

Sestavite funkcijo slike(permutacija, x, n), ki vrne zaporedje slik, ki ga dobimo, če začnemo s številom x in na njem n-krat uporabimo permutacijo permutacija.

>>> slike({1: 3, 2: 4, 3: 2, 4: 1}, 1, 2)
[1, 3, 2]

Uradna rešitev

def slike(permutacija, x, n):
    # Funkcijo definiramo rekurzivno. Če je n > 0, naredimo sliko y, nato
    # pa dodamo še seznam n - 1 slik elementa y.
    if n == 0:
        return [x]
    else:
        y = permutacija[x]
        ostale = slike(permutacija, y, n - 1)
        return [x] + ostale
    
def slike_nerekurzivno(permutacija, x, n):
    r=[]
    for i in range(n+1):
        r.append(x)
        x = permutacija[x]
    return r

4. podnaloga

Sestavite funkcijo cikel(permutacija, x), ki vrne celoten cikel, ki se začne s številom x.

>>> cikel({1: 3, 2: 2, 3: 1}, 1)
[1, 3]
>>> cikel({1: 3, 2: 2, 3: 1}, 2)
[2]

Uradna rešitev

def cikel(permutacija, x):
    # Dokler slika zadnjega elementa, ki smo ga dodali v cikel, ni enaka
    # začetnemu elementu y, dodamo sliko ter ponavljamo.
    cikel = [x]
    y = permutacija[x]
    while y != x:
        cikel.append(y)
        y = permutacija[y]
    return cikel

5. podnaloga

Sestavite funkcijo cikli(permutacija), ki vrne seznam disjunktnih ciklov dane permutacije. Vsak cikel naj se začne z najmanjšim številom v ciklu, cikli pa naj bodo urejeni po začetnem številu.

>>> cikli({1: 3, 2: 2, 3: 1})
[[1, 3], [2]]

Uradna rešitev

def cikli(permutacija):
    # V seznam izracunaniCikli si shranjujemo do sedaj izračunane cikle, v seznam
    # ugotovljena pa vsa tista števila, za katera smo že ugotovili, kateremu
    # ciklu pripadajo.
    izracunaniCikli = []
    ugotovljena = []
    # Nato gremo zaporedoma čez vsa števila od 1 do n. Če za neko število
    # še nismo ugotovili, kam spada, je najmanjše v svojem ciklu. Zato
    # izračunamo njegov cikel, ga dodamo k ciklom, vsa števila iz cikla pa
    # dodamo med ugotovljena.
    for i in range(1, len(permutacija) + 1):
        if i not in ugotovljena:
            c = cikel(permutacija, i)
            izracunaniCikli.append(c)
            ugotovljena.extend(c)
    return izracunaniCikli

Ljubezen nam je vsem v pogubo II

Socialno omrežje zaljubljenosti podamo s slovarjem, ki ime osebe preslika v množico vseh, v katere je oseba zaljubljena (ena oseba je lahko zaljubljena v več oseb). Na primer, slovar

s = {'Ana' : {'Bine','Cene'},
     'Bine' : set(),
     'Cene' : {'Bine'},
     'Davorka' : {'Davorka'},
     'Eva' : {'Bine'}}

nam pove, da je Ana zaljubljena v Bineta in Cenete, Bine ni zaljubljen, Cene ljubi Bineta, Davorka samo sebe in Eva Bineta.

   Opomba*: Naloga je podobna nalogi"Ljubezen nam je vsem v pogubo", le da so tukaj ljubljene osebe v množici in ne v seznamu. Prav tako moramo vračati množice!_

1. podnaloga

Sestavite funkcijo narcisoidi(d), ki sprejme slovar zaljubljenih in vrne monžico tistih, ki ljubijo same sebe.

Uradna rešitev

def narcisoidi(d):
    return {oseba for oseba in d if oseba in d[oseba]}

2. podnaloga

Sestavite funkcijo ljubljeni(d), ki sprejme slovar zaljubljenih in vrne množico tistih, ki so ljubljeni.

Uradna rešitev

def ljubljeni(d):
    return {ljubljen for oseba in d for ljubljen in d[oseba]}

3. podnaloga

Sestavite funkcijo pari(d), ki sprejme slovar zaljubljenih in vrne množico vseh parov, ki so srečno ljubljeni. Vsak par naj se pojavi samo enkrat in sicer tako, da je sta zaljubljenca našteta po abecedi. Na primer, če sta Ana in Bine zaljubljena, dodamo par ('Ana','Bine').

Uradna rešitev

def pari(d):
    return {tuple(sorted((x, y))) for x in d for y in d[x] if x in d[y]}

4. podnaloga

Sestavite funkcijo ustrezljivi(oseba, d), ki sprejme ime osebe ter slovar zaljubljenih, vrne pa množico vseh ljudi, ki so do dane osebe še posebej ustrežljivi. Posebej ustrežljivi so seveda za to, ker so bodisi zaljubljeni v dano osebo, bodisi so zaljubljeni v osebo, ki je posebej ustrežljiva do nje, in tako naprej.

Na primer, če imamo slovar

s = {'Ana' : {'Bine', 'Cene'},
     'Bine' : {'Ana'},
     'Cene' : {'Bine'},
     'Davorka' : {'Davorka'},
     'Eva' : {'Bine'}}

so do Ceneta posebej ustrežljivi Ana (ki je zaljubljena vanj), Bine (ki je zaljubljen v Ano), Eva (ki je zaljubljena v Bineta), ter seveda Cene, ki je zaljubljen v Evo.

Uradna rešitev

def ustrezljivi(oseba, d):
    # seznam, v katerega nabiramo ustrežljive osebe
    ustrezljivi = set()
    # najprej dodamo tiste, ki ljubijo prvo osebo
    dodani = {o for o in d if oseba in d[o]}
    # dokler smo koga dodali, dodajamo ustrežljive
    while dodani:
        ustrezljivi.update(dodani)
        # sedaj pa dodajamo tiste, ki ljubijo nazadnje dodane osebe
        dodani = {o for o in d for dodan in dodani
                  if dodan in d[o] and o not in ustrezljivi}
    return ustrezljivi

Imena

V neki datoteki, ki ima lahko več vrstic, so zapisana imena. Znotraj posamične vrstice so imena ločena z vejicami (brez presledkov). Primer take datoteke:

Jaka,Peter,Miha,Peter,Anja
Franci,Roman,Renata,Jožefa
Pavle,Tadeja,Arif,Filip,Gašper

1. podnaloga

Sestavite funkcijo kolikokrat_se_pojavi(niz, ime), ki vrne število pojavitev imena ime v nizu imen niz.

>>> kolikokrat_se_pojavi('Alojz,Samo,Peter,Alojz,Franci', 'Alojz')
2

Uradna rešitev

def kolikokrat_se_pojavi(niz, ime):
    return niz.split(',').count(ime)

# Alternativna rešitev (brez uporabe metode count)
def kolikokrat_se_pojavi_alt(niz, ime):
    vsa_imena = niz.split(',')
    stevec = 0
    for s in vsa_imena:
        if s == ime:
            stevec += 1
    return stevec

2. podnaloga

Sestavite funkcijo koliko(niz, datoteka), ki na izhodno datoteko z imenom datoteka za vsako ime zapiše, kolikokrat se pojavi v nizu niz.

Na primer, če je niz enak 'Jaka,Luka,Ante,Luka', naj funkcija v izhodno datoteko zapiše

Jaka 1
Luka 2
Ante 1

Pozor: Imena naj bodo izpisana v takem vrstnem redu, kakor si sledijo njihove prve pojavitve v nizu niz.

Uradna rešitev

def koliko(niz, datoteka):
    imena = niz.split(',')
    brez_ponovitev = []
    for ime in imena:
        if ime not in brez_ponovitev:
            brez_ponovitev.append(ime)
    with open(datoteka, 'w', encoding='utf-8') as f:
        for ime in brez_ponovitev:
            print(ime, imena.count(ime), file=f)

# Alternativna rešitev
def koliko_alt(niz, datoteka):
    imena = []
    stevci = []
    for ime in niz.split(','):
        if ime not in imena:
            imena.append(ime)
            stevci.append(1)
        else:
            stevci[imena.index(ime)] += 1
    with open(datoteka, 'w', encoding='utf-8') as f:
        for ime, stevec in zip(imena, stevci):
            print(ime, stevec, file=f)

# Še ena možna rešitev (z uporabo slovarja)
def koliko_alt2(niz, datoteka):
    imena = niz.split(',')
    stevec = {}
    for ime in imena:
        stevec[ime] = stevec.get(ime, 0) + 1
    with open(datoteka, 'w', encoding='utf-8') as f:
        for ime in imena:
            if ime not in stevec:
                continue
            print(ime, stevec[ime], file=f)
            del stevec[ime]

3. podnaloga

Sestavite funkcijo koliko_iz_datoteke(vhodna, izhodna), ki naj naredi isto kot funkcija koliko, le da podatke prebere iz datoteke. Torej, na izhodno datoteko z imenom izhodna naj za vsako ime zapiše, kolikokrat se pojavi v datoteki z imenom vhodna.

Pozor: Vhodna datoteka ima lahko več vrstic. Imena izpišite v enakem vrstnem redu, kot si sledijo njihove prve pojavitve v datoteki vhodna.

Uradna rešitev

def koliko_iz_datoteke(vhodna, izhodna):
    vrstice = []  # Seznam vseh vrstic v datoteki vhodna.
    with open(vhodna, encoding='utf-8') as f:
        for vrstica in f:
            vrstice.append(vrstica.strip())  # Odstranimo '\n' s konca vrstice.
    imena = ','.join(vrstice)  # Niz z vsemi imeni iz datoteke.
    koliko(imena, izhodna)

4. podnaloga

Sestavite funkcijo koliko_urejen(vhodna, izhodna), ki na izhodno datoteko z imenom izhodna za vsako ime zapiše, kolikokrat se pojavi v datoteki z imenom vhodna. Imena naj bodo urejena padajoče po frekvenci pojavitev. Imena, ki imajo enako frekvenco, naj bodo nadalje urejena leksikografsko (tj. po abecednem vrstnem redu).

Primer: Če je na datoteki imena_vhod.txt vsebina

Luka,Jaka
Luka,Miha,Miha
Miha,Aleš,Aleš

naj bo po klicu funkcije koliko_urejen('imena_vhod.txt', 'imena_izhod.txt') na datoteki imena_izhod.txt naslednja vsebina:

Miha 3
Aleš 2
Luka 2
Jaka 1

Uradna rešitev

def koliko_urejen(vhod, izhod):
    imena = []  # Seznam vseh imen.
    brez_ponovitev = []  # Seznam imen brez ponovitev.
    with open(vhod, encoding='utf-8') as f:
        for vrstica in f:
            for ime in vrstica.strip().split(','):
                imena.append(ime)
                if ime not in brez_ponovitev:
                    brez_ponovitev.append(ime)
    # Seznam pari bo vseboval pare oblike (-3, 'Miha'). Druga komponenta bo
    # ime; prva komponenta bo število pojavitev tega imena, pomnoženo z -1.
    pari = []
    for ime in brez_ponovitev:
        pari.append((-imena.count(ime), ime))
    # Metoda sort uredi števila naraščajoče po vrednosti, nize pa leksikografsko
    # (tj. tako kot so urejeni v leksikonu). Pare uredi glede na prvo komponento,
    # tiste z enako prvo komponento pa še glede na drugo komponento.
    pari.sort()
    with open(izhod, 'w', encoding='utf-8') as f:
        for s, ime in pari:
            print(ime, -s, file=f)

# Alternativna rešitev (uporablja izpeljane sezname, množice in lambda funkcije)
def koliko_urejen_alt(vhod, izhod):
    with open(vhod, encoding='utf-8') as f:
        imena = ','.join([vrstica.strip() for vrstica in f])
    enkrat_imena = set(imena.split(','))
    pari = [(ime, kolikokrat_se_pojavi(imena, ime)) for ime in enkrat_imena]
    pari.sort(key=lambda p: (-p[1], p[0]))
    with open(izhod, 'w', encoding='utf-8') as f:
        for ime, s in pari:
            print(ime, s, file=f)

LEGO kocke

Vsako LEGO kocko lahko opišemo z dvema lastnostima: tipom (torej obliko) in barvo.

Če boste nalogo uspešno rešili še pred koncem, si lahko ogledate seznam vseh možnih barv kock, pri tej nalogi pa bomo predpostavili le tri barve: rdečo, modro in rumeno. Tipov LEGO kock pa je ogromno, zato jih bomo predstavili kar z nizi kot na primer '2x2', '4x1-tanka' ali pa 'nogice'. Sprejmimo dogovor, da nobeno ime tipa ne vsebuje pike.

1. podnaloga

Vsebino škatle podamo s seznamom vseh kock, ki so v njej. Vsaka kocka je opisana z nizom, ki vsebuje tip kocke in barvo, ki sta ločeni s piko. Npr. kocka tipa '2x2' rdeče barve je predstavljena z nizom '2x2.rdeča'.

Napišite funkcijo slovar_kock(skatla), ki dobi seznam skatla in sestavi slovar vsebovanih kock, urejen po tipih ter po barvah, kot prikazuje primer:

>>> slovar_kock(['2x2.rdeča', '2x2.rdeča', 'nogice.modra', '2x2.modra'])
{'nogice': {'modra': 1}, '2x2': {'rdeča': 2, 'modra': 1}}

Uradna rešitev

def slovar_kock(skatla):
    '''Vrne slovar lego kock'''
    sk = dict()
    for kocka in skatla:
        tip, barva = kocka.split('.')
        if tip not in sk:
            sk[tip] = dict()
        sk[tip][barva] = sk[tip].get(barva, 0) + 1
    return sk

2. podnaloga

Napišite funkcijo lahko_sestavimo(skatla, model), ki dobi dva slovarja kock, in vrne True natanko tedaj, ko je možno modelček (za katerega potrebujemo kocke, ki so podane s slovarjem model) sestaviti s kockami, ki so v škatli.

>>> model = {'4x1': {'modra': 1}, '2x2': {'rdeča': 2, 'modra': 1}}
>>> skatla = {'4x1': {'modra': 3, 'rdeča': 2}, '2x2': {'rdeča': 4, 'modra': 1, 'rumena': 5}}
>>> lahko_sestavimo(skatla, model)
True
>>> model_2 = {'4x1': {'rumena': 1}, '2x2': {'rdeča': 1, 'rumena': 2}}
>>> lahko_sestavimo(skatla, model_2)
False

Uradna rešitev

def lahko_sestavimo(skatla, model):
    '''Ali lahko sestavimo model, če imamo na voljo škatlo kock skatla'''
    for tip, barve in model.items():
        for barva, cnt in barve.items():
            if cnt > skatla.get(tip, {}).get(barva, 0):
                return False
    return True

3. podnaloga

Napišite funkcijo hitro_sestavljanje(skatla, model), ki vrne True, če je možno modelček sestaviti “na hitro”, torej tako, da barve niso pomembne (še vedno pa je pomembno, da uporabimo kocke ustreznega tipa).

>>> model = {'4x1': {'modra': 2}, '2x2': {'rdeča': 2, 'modra': 1}}
>>> skatla_1 = {'4x1': {'rdeča': 3}, '2x2': {'rdeča': 1, 'rumena': 5}}
>>> skatla_2 = {'4x1': {'rumena': 3, 'rdeča': 2}, '2x2': {'rumena': 1, 'rdeča': 1}}
>>> hitro_sestavljanje(skatla_1, model)
True
>>> hitro_sestavljanje(skatla_2, model)
False

Uradna rešitev

def hitro_sestavljanje(skatla, model):
    '''Ali lahko "na hitro"(brez upoštevanja barv)
       sestavimo model iz kock v škatli skatla
    '''
    for tip, barve in model.items():
        if sum(barve.values()) > sum(skatla.get(tip, {}).values()):
            return False
    return True